Visão geral

• Resultados muito interpretáveis
• Particionamento recursivo do espaço das covariáveis
• Imita, muito vagamente, processos cognitivos de tomadas de decisão
• Lidam bem com covariáveis qualitativas e quantitativas
• Proder preditivo usualmente menor que o de outros métodos
• Usualmente são não robustas: uma pequena mudança nos dados pode levar a estimativas muito discrepantes
  • Tentaremos contornar esses problemas

Um exemplo

Figura 4.6 de [AME]

Um exemplo mais concreto

Figura 4.7 de [AME]: Regressão do salário de um indivíduo dadas as covariáveis idade e anos de estudo.

Formalizando

• Partição do espaço das covariáveis
  • Regiões \(R_1, \dots, R_j\) distintas disjuntas
  • A predição para a resposta \(Y\) de uma observação \(\mathbf{x}\) que está na região \(k\) é a média das respostas cujos respectivos \(\mathbf{x}\) também estão nessa região: \[g(\mathbf{x}) = \frac{1}{\#\{i ~ | ~ \mathbf{x}_i \in R_k\}} \sum_{i ~ | ~ \mathbf{x}_i \in R_k} y_i.\]

Formalizando

• Criação em duas etapas:
  1. Criação de uma árvore “completa” e “complexa”
     • Árvores puras
     • Partições onde os valores de \(Y\) no conjunto de treinamento em cada folha sejam “homogêneos”
  2. Poda da árvore para evitar sobreajuste
     • Reduzir a complexidade da árvore
     • Remover nós “desnecessários”

Etapa 1: Criação da árvore

• Medida de plausibilidade de uma árvore \(T\): erro quadrático médio: \[\mathcal{P}(T) = \frac{1}{n} \sum_R \sum_{i ~ | ~ \mathbf{x}_i \in R} (y_i - \widehat{y}_R)^2\]
• \(\widehat{y}_R\): valor predito para a resposta de uma observação em \(R\)
• \(\displaystyle \mathrm{arg}\min_T \mathcal{P}(T)\) \(\Rightarrow\) estudar todas as partições! Inviável
• Heurística simplificadora: divisão binária recursiva

Etapa 1: Criação da árvore

Figura 8.3 de [ITSL]: Particionamento proveniente de divisão binária recursiva (direita) e particionamento mais geral (esquerda)

Etapa 1: Criação da árvore

• Particionar o espaço de covariáveis em duas regiões
  • Busca de covariável \(x_i\) e corte \(t_1\)
  • Partição \((R_1, R_2)\) com predições de menor EQM: \[\sum_{i ~ | ~ \mathbf{x}_i \in R_1} (y_i - \widehat{y}_{R_1})^2 + \sum_{i ~ | ~ \mathbf{x}_i \in R_2} (y_i - \widehat{y}_{R_2})^2\]
  • \(R_1 = \{\mathbf{x} ~ | ~ x_i < t_1\}\) e \(R_2 = \{\mathbf{x} ~ | ~ x_i \geq t_1\}\)

Etapa 1: Criação da árvore

Figura 4.8 de [AME]: a) Onde chegamos com o passo-a-passo anterior; b) onde queremos chegar no próximo passo

• Nó inicial fixado
• Particionar \(R_1\) ou \(R_2\) em regiões menores
• Repetir a estratégia

Etapa 1: Criação da árvore

• Particionar \(R_1\) ou \(R_2\) em regiões menores
  • Busca de covariável \(x_j\) e corte \(t_2\)
  • Decidir qual região particionar, \(R_1\) ou \(R_2\)
  • Sempre para minimizar o EQM
• Assumindo escolhida a região \(R_1\), temos: \[R_{1,1} = \{\mathbf{x} ~ | ~ x_i < t_1, x_j < t_2\}\] \[R_{1,2} = \{\mathbf{x} ~ | ~ x_i < t_1, x_j \geq t_2\}\] \[R_2 = \{\mathbf{x} ~ | ~ x_i \geq t_1\}\]

Etapa 1: Criação da árvore

Figura 4.8 de [AME]: b) Onde chegamos com o passo-a-passo anterior; c) d) continuações hipotéticas do processo

• Continuar até cada folha ter “poucas” observações

Etapa 1: Criação da árvore

Figura 8.3 de [ITSL]: Árvore (esquerda) e gráfico da função \(g\) correspondente (direita)

Um exemplo até aqui

Um exemplo até aqui

scikit-learn - DecisionTreeRegressor

DTR = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5)
DTR.fit(x_tr.reshape(-1, 1), y_tr)
print('ATENÇÃO: Diversos hiperparâmetros para ajustar!')

ATENÇÃO: Diversos hiperparâmetros para ajustar!

Etapa 2: Poda da árvore

• Retirar nós da árvore para melhorar sua capacidade preditiva
  • Como escolher os nós a serem removidos?
• Poda por custo de complexidade
  • Ideia reminiscente do Lasso
  • Árvore “grande” \(T\) e hiperparâmetro \(\alpha\)
  • Sub-árvore \(T_{\alpha} \subset T\) que minimiza \[\sum_{m = 1}^{|T_{\alpha}|} \sum_{i ~ | ~ \mathbf{x}_i \in R_m} (y_i - \widehat{y}_{R_m})^2 + \alpha |T_{\alpha}|\]

Etapa 2: Poda da árvore

• Sub-árvore \(T_{\alpha} \subset T\) que minimiza \[\sum_{m = 1}^{|T_{\alpha}|} \sum_{i ~ | ~ \mathbf{x}_i \in R_m} (y_i - \widehat{y}_{R_m})^2 + \alpha |T_{\alpha}|\]
  • \(|T_{\alpha}|\): número de nós terminais da árvore
  • \(R_m\): região correspondente ao \(m\)-ésimo nó terminal
• \(\alpha\) controla equilíbrio entre complexidade e ajuste aos dados (encontrado por validação cruzada)
• Poda diminui variância mas aumenta o viés

Continuando no exemplo

DTR = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5,
                            ccp_alpha = 0.01)
DTR.fit(x_tr.reshape(-1, 1), y_tr);

Escolhendo \(\alpha\) por validação cruzada

DTR = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5)
param_grid_DTR = {"ccp_alpha": [0.0001, 0.0001, 0.001, 0.01, 0.03, 0.05, 0.07, 0.1, 0.2]}
DTRCV = GridSearchCV(DTR, param_grid = param_grid_DTR, scoring='neg_mean_squared_error', cv = 5)

DTRCV.fit(x_tr.reshape(-1, 1), y_tr)
print(DTRCV.best_estimator_)

DecisionTreeRegressor(ccp_alpha=0.01, min_samples_leaf=5)

Árvores vs. modelos lineares

• Modelos lineares: \(\displaystyle g(\mathbf{x}) = \beta_0 + \sum_{i = 1}^{p} \beta_i x_i\)
• Árvores: \(\displaystyle g(\mathbf{x}) = \sum_{m = 1}^{M} c_m \mathbb{I}_{R_m}(\mathbf{x})\)
  • \(\mathbb{I}_A\) função indicadora do conjunto \(A\)
  • \(R_1, \dots, R_M\) partição do espaço de covariáveis
  • Mais adequada para capturar relações não-lineares entre as covariáveis e a resposta

Uma floresta aleatória… 🙂

Visão de ambos os métodos

• Agregar \(B\) árvores para melhorar o poder preditivo
• Bagging
  • Gerar árvores através de amostras bootstrap dos dados
  • Funciona para outros modelos, não somente árvores
• Florestas aleatórias
  • Gerar árvores através de amostras bootstrap dos dados
  • Crescer a árvore com “mais cuidado”

Bagging

• Contexto de regressão, duas funções de predição: \(g_1\) e \(g_2\)
  • Riscos condicionados em \(\mathbf{x}\) mas não na amostra de treinamento \(\Rightarrow\) \(\mathbb{E} = \mathbb{E}_{\mathcal{D}, Y}\) \[\mathbb{E}\left[ \left. \left(Y - g_1(\mathbf{x})\right)^2 \right| \mathbf{x} \right] \quad \text{e} \quad \mathbb{E}\left[ \left. \left(Y - g_2(\mathbf{x})\right)^2 \right| \mathbf{x} \right]\]
  • Estimador combinado \(\displaystyle g(\mathbf{x}) = \frac{g_1(\mathbf{x}) + g_2(\mathbf{x})}{2}\)
  • Sob certas hipóteses: \(\displaystyle \mathbb{E}\left[ \left. \left(Y - g(\mathbf{x})\right)^2 \right| \mathbf{x} \right] \leq \mathbb{E}\left[ \left. \left(Y - g_i(\mathbf{x})\right)^2 \right| \mathbf{x} \right], i = 1, 2\)

Bagging

• Generalizar para \(B\) funções de predição: \[g(\mathbf{x}) = \frac{1}{B} \sum_{b = 1}^{B} g_b(\mathbf{x})\]
  • \(g_b\) geradas através de amostras bootstrap
    • \(\mathbf{x}_1, \dots, \mathbf{x}_n\) conjunto de treinamento
    • \(\mathbf{x}_{i_1}, \dots, \mathbf{x}_{i_n}\) amostras com reposição do conjunto de treinamento \(\Rightarrow\) amostra bootstrap
    • Usar esse conjunto para estimar \(g_b\)

Bagging - atenção!

• As \(g_b\) precisam ser não-viesadas \(\Rightarrow\) não podar as árvores!
• As \(g_b\) precisam ser descorrelacionadas \(\Rightarrow\) isso é um problema, na verdade…
  • Florestas aleatórias tentam resolvê-lo
  • Mas vejamos uma coisa de cada vez!

Um exemplo

scikit-learn - BaggingRegressor

DTB = BaggingRegressor(estimator = DecisionTreeRegressor(max_depth = None, min_samples_leaf = 5), n_estimators = 1000)
print('ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!')

ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!

Fechando o bagging

• Menos interpretável que árvores de regressão
• Potencialmente maior poder preditivo
• Permite criar uma medida de importância para cada covariável

Medindo a importância dos atributos

Medindo a importância dos atributos

• Primeiramente, calcula-se o RSS para todos os nós gerados com base em determinado atributo
• Repete-se para todas as árvores
• Calcula-se a média dessa redução \(\Rightarrow\) medida de importância do atributo
• Específico de árvores \(\Rightarrow\) não está implementado em BaggingRegressor no scikit-learn
• Está implementado em DecisionTreeRegressor, RandomForestRegressor e seus equivalentes para classificação (atributo feature_importances_)

Um exemplo

scikit-learn - make_regression

X, y = make_regression(n_samples = 1000, n_features = 100,
                       n_informative = 10, n_targets = 1, noise = 1)
DT_importance = RandomForestRegressor(n_estimators = 100, max_depth = None,
                                      min_samples_leaf = 5, max_features = None)
print('Florestas aleatórias com \'max_features = None\' é equivalente ao bagging!')
print('Vamos ver florestas aleatórias logo a seguir')

Florestas aleatórias com 'max_features = None' é equivalente ao bagging!
Vamos ver florestas aleatórias logo a seguir

Florestas aleatórias

• Bagging
  • \(g_b\) construídos a partir de amostras bootstrap
  • Estimadores correlacionados!
• Florestas aleatórias visam diminuir essa correlação
  • Criar um novo nó da árvore
  • Escolher não mais uma dentre as \(p\) covariáveis
  • Escolher uma dentre \(m < p\)
  • \(m\) candidatas escolhidas aleatoriamente
  • \(m \approx p/3\) ou \(\sqrt{p}\) leva a bons resultados

Um exemplo

scikit-learn - RandomForestRegressor

RF = RandomForestRegressor(n_estimators = 1000, max_depth = None, min_samples_leaf = 5, max_features = 'log2')
print('ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!')
print('SÓ TEMOS UM ATRIBUTO!!!! É equivalente ao bagging.')

ATENÇÃO: Diversos hiperparâmetros para ficar atento/a!
SÓ TEMOS UM ATRIBUTO!!!! É equivalente ao bagging.